package DataStructure;

//并查集,存储多个集合,支持集合合并,集合查询
public class UFSet {
    private int[] parent;//存储索引节点的父节点
    private int[] size;//存储索引节点所代表集合的节点个数
    private int N;//集合个数

    public UFSet(int n) {
        this.N = n;
        this.parent=new int[n];
        this.size=new int[n];
        //初始化,每个节点各为一组
        for (int i = 0; i < n; i++) {
            parent[i]=i;
            size[i]=1;
        }
    }
    //获取集合个数
    public int count(){
        return N;
    }
    //查询元素所在集合
    private int find(int e){
        if(e == parent[e])
            return e;
        return parent[e]=find(parent[e]);//查询父节点的集合,并将根节点设为其父节点(路径压缩)
    }
    //查询两个元素是否在同一集合
    public boolean isConnected(int p,int q){
        return find(p)==find(q);
    }
    //将两个元素代表的集合合并
    public void union(int p,int q){
        if(isConnected(p,q))
            return;
        int proot=find(p);
        int qroot=find(q);
        //将节点较少的集合合并到较多的集合
        if(size[proot]<size[qroot]){
            parent[proot]=qroot;
            size[qroot]+=size[proot];
        } else {
            parent[qroot] = proot;
            size[proot]+=size[qroot];
        }
        N--;
    }
}
